We started looking at a class of algorithms called search algorithms yesterday.

This is kind of the most basic set of algorithms, AI algorithms.

They're predicated, you can only apply them if you can formulate the search problem as a set of states,

a set of actions that actually get you from state to state, and some criterion on whether you've hit a goal state.

If you have that, and possibly a cost function, then you're in business.

You can just take one of these algorithms that we looked at yesterday from the shelf, apply it, and everything works.

The research procedure is very simple. You are in a node, you have a fringe, you have a set of nodes that you have looked at before,

you've computed before but not expanded, then you are in a node, you check whether you're in a goal node, if yes, everything is fine.

If the fringe is empty, you fail. If there's a fringe and you're not in a goal node, you essentially choose a node,

new node from the fringe, expand it, add those to the fringe, and you're done.

We recursively loop over this all the time.

We talked about, oh yeah, we have these nice little examples, one thing we talked about that's important to realize here is that

we are actually not in the state space itself, we are in a state tree which we're exploring.

Essentially, rather than have the complicated graph algorithms, we kind of unfold the graph into a tree from the perspective of the initial node.

Which brings us a couple of problems, namely we might have repeated states because different states may actually appear multiple times in the tree,

but it gives us a very, very, very simple algorithm that we can readily implement, and I think you already have implemented it in Prolog.

Which for some of the strategies is easier than for others, as you will have discovered.

Okay, we will always in this course try and keep tabs on how bad our algorithms are.

Okay, so we're going to evaluate our algorithms essentially with these four properties in mind.

One is, do we always find a solution if one exists, just completeness, then we look at time and space complexity,

and then if we have cost functions we can worry about optimality.

Do we find the optimal solution at all, and do we find the best solutions first?

Actually, best solutions first are what we really want, because if we have an algorithm that guarantees that, then we know we can stop after finding one solution.

And very often we find the first solution, if it's here, after exploring a very small part of the search tree.

If we know we can stop now, we can leave out all of that stuff.

And for that reason, optimality is important.

There are three parameters we have in our considerations.

One is the branching factor of the search tree, and I want to come back on this.

The branching factor is not how big this is, or how many branches you have in the tree.

But for the inner nodes, you look at how many children they have, and then you look at the maximal value for that.

All of the synthetic trees I have in my examples are binary, which means they have a branching factor of 2.

And Romania, I think, has a branching factor of 4, which means if you're in a city, there are at most four cities that are connected to it.

There are other problems which have higher branching factors.

Think of chess.

You typically have something like eight pieces or something like that, which you can move deeper into the game.

You might even have more. So there we have, I don't know, a branching factor of 15 or something like that.

Which, of course, makes the trees extremely bushy and the search space extremely big.

Then we have the minimal depth to the shallower solution.

That's one thing that we're interested in.

And the maximal depth of the search space.

All of those potentially go into our considerations of time and space complexity and possibly optimality and completeness as well.

Are there any questions?

I will be very explicit about complexities here in the beginning.

I'll kind of relent a little bit as we go along.

Complexity considerations will play a great role.

And to give you the sad news first, everything we do will in principle be exponential with a couple of little examples,

which means we have to do something about it because exponential means we're not going to solve it.

We have in principle an algorithm and it works for small examples, but for big examples it doesn't.

And one thing we talked about as well is the shape of trees.

And I kind of made this picture, which is really, really, really, really important for you to get.